package medium组合总和;

import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<List<Integer>> l = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        combination(list,list1,candidates,0,0,target);
        for (List<Integer> lt:list
        ) {
            if (!l.contains(lt))
                l.add(lt);
        }
        return l;
    }
    public void combination(List<List<Integer>> list, List<Integer> list1, int[] candidates, int i, int sum, int target){
        if (i < candidates.length && sum <= target){
            if (sum == target ){
                list.add(list1);
            }
            List<Integer> lst = new ArrayList<>(list1);
            lst.add(candidates[i]);
            sum = sum+candidates[i];
            combination(list,lst,candidates,i,sum,target);
            List<Integer> lst1 = new ArrayList<>(lst);
            lst1.remove(lst1.size()-1);
            sum = sum-candidates[i];
            combination(list,lst1,candidates,i+1,sum,target);
        }
    }
    @Test
    public void test(){
        int[] num = {2,3,5};
        List<List<Integer>> list = combinationSum(num,8);
        for (List<Integer> list1:
             list) {
            System.out.println(list1.toString());
        }
    }
}
